home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Monster Media 1994 #2
/
Monster Media No. 2 (Monster Media)(1994).ISO
/
prog_c
/
tpchal_1.zip
/
ANALYSIS.TXT
next >
Wrap
Text File
|
1994-06-09
|
9KB
|
226 lines
------------------------------------------------------------------------------
Date: Sun May 22 1994 14:36:16
From: Andrew Key
To: All
Subj: A simple programming challenge
Attr:
international C echo
-------------------------------
You can take advantage of a few divisibility rules when coding for an
efficient solution, or when solving with pen and paper.
Divisible by 2: ones digit will be even.
Divisible by 3: sum of digits will also be divisible by 3.
Divisible by 4: last two digits (ie. ones and tens digits) will by div. by 4.
Divisible by 5: ones digit will be a zero or a five.
Divisible by 6: ones digit will be even, and sum of digits will be div. by 3.
Divisible by 8: last three digits will be div. by 8.
Divisible by 9: sum of digits will also be divisible by 9.
Additionally, since zero may not be used, the 5th digit must be a five.
And using 1 through 9, each once, guarantees that any number we select
will be divisible by nine. So once we have eight digits that meet the
criteria, just add the digit not used to complete the ninth digit.
Another thing to note is that none of the odd-numbered digits may
contain 2, 4, 6, or 8; all four possible even numbers will be used in
the even-numbered digits.
We'll start with the first three digits, remembering that digit two must
be even and non-zero, and that none of the digits can repeat. Also, since
the fifth digit must be five, we can eliminate any that contain it.
The possibilities are:
123 129 147 183 189 321 327 369 381 387 723 729 741 783
789 921 927 963 981 987
So, immediately, we've narrowed down our search to 20 initial branches
that the number could take. Now we start looking for possiblities for
the fourth and fifth digit. We need only test the last two digits for
of a four digit number, and then add our five as a fifth digit to the
ones that pass - of course striking out any zeros, repeats. This gives
us:
12965 14725 14765 18325 18365 18925 18965 32165 32765 36925
38125 38165 38725 38765 72365 72965 74125 74165 78325 78365
78925 78965 92165 92765 96325 98125 98165 98725 98765
This gives us a total of 29 5-digit numbers that meet all criteria so
far. Now, to test for the sixth digit, we look for even numbers, and the
resulting number must be divisible by three. Since the first three digits
have already been determind to be divisible by three, we need only test the
last two. And since the 2nd and 4th digits are even, and the 6th digit must
be also, there are only two possibilities to test per number. This gives
us:
147258 183654 189654 321654 327654 369258 381654 387654 723654
729654 741258 783654 789654 921654 927654 963258 981654 987654
At this point, 3 of 4 possible even numbers have been used in each
number and 3 of 5 odd numbers possible have been selected. So we know
that our possible answers will take this form(x represents unknown):
147258x6x 183654x2x 189654x2x 321654x8x 327654x8x 369258x4x
381654x2x 387654x2x 723654x8x 729654x8x 741258x6x 783654x2x
789654x2x 921654x8x 927654x8x 963258x4x 981654x2x 987654x2x
At this point, substitute in our remaining odd numbers for digit 7 and
test digits 6-8 for divisibility by 8(We'll check for divisibility by
7 next). And if a number passes the div. by 8, we'll go ahead and put
the remaining number in the 9th position. We are left with:
147258963 183654729 189654327 189654723 381654729 741258963
789654321 981654327 981654723 987654321
Now we check the remaining numbers for divisibility by seven. We saved
this test for last, as there are no shorter tests that we can apply than
to actually divide the whole number by 7. The only number whose first
seven digits are evenly divisible by 7 is:
318654729
Of course, it's a simple matter to write code to take advantage of the
divisibility rules. Following along these lines, you should be able to
code a pretty *fast* algorithm.
-AK
------------------------------------------------------------------------------
Date: Sat May 21 1994 00:12:04
From: Auke Reitsma
To: Jeff Dunlop
Subj: A simple programming cha
Attr:
international C echo
-------------------------------
My 'program' -- heavily optimized ;-) -- is:
#include <stdio.h>
main( void )
{
puts( "The answer is: 381,654,729\n" );
}
Actually found this 'manually' within an hour. Method:
Consider ABCDEFGHI to represent the nine digit number, and each
letter an unique digit.
1 As AB must be divisible by 2, B must be even. And similar for D,
F, and H. Therefore A, C, E, G and I must be odd.
2 As ABCDE must be divisible by five, it IS five.
3 ABC must be divisible by three. Therefore (A+B+C) mod 3 == 0.
ABCDEF must be divisible by six. So also by three.
So (A+B+C+D+E+F) mod 3 == 0. Therefore (D+E+F) mod 3 == 0.
Similarly: (G+H+I) mod 3 == 0.
4 As E = 5, the only valid pairs of digits for D and F are
4 and 6 or 2 and 8.
C is odd, so D cannot be 4 or 8 as ABCD must be divisible
by 4. So D=6 and F=4 or D=2 and F=8. In each case B and H are
the remaining even digits.
5 ABCDEFGH must be divisible by eight. Therefore FGH must be
divisible by eight. F is even and G is odd, so H cannot be 4
or 8 (G4 / 2 = X7, G8 / 2 = X9). At this point the only
possible values are A4C258G6I and A8C654G2I.
After trying G = 1, 3, 7 or 9 and checking FGH/8:
A4C25816I, A4C25896I, A8C65432I and A8C65472I.
6 And after (respectively) trying I = the remaining digits:
(with G+H+I mod3 == 0)(see 3):
A4C258963, A8C654321, A8C654327, A8C654723 and A8C654729.
7 Filling in all remaining possible values for A and C:
147258963, 789654321, 189654327, 189654723, 183654729,
741258963, 987654321, 981654327, 981654723 and 381654729.
8 Now check each of these numbers for divisibility by 7 of the
number consisting of the first seven digits.
Only 381654729 satisfies this test and therefore is the
ONLY solution.
Note that division by nine is always possible!
Greetings from Delft, The Netherlands,
Auke Reitsma.
------------------------------------------------------------------------------
Date: Mon May 23 1994 15:19:48
Date: Mon May 23 1994 15:19:48
From: Stephen Lindholm
To: Rhys Wong
Subj: A SIMPLE PROGRAMMING CHAL
Attr:
international C echo
-------------------------------
Whoa! This is probably the longest paper you'll see from me in this echo that
doesn't have any code in it. :)
RW> Solving the problem is not so challenging, but writing a program to solve
RW> the problem IS !
You can either have it plug through all of the combos or optimize it as much as
possible. It would take about thrice as long to do the latter. If I had access
to a computer (well, a real computer, I was in typing class which is in the
Apple 2 lab... :) while during it, I would only have used it to check
divisibility by 7.
RW> I don't understand why the odds have 4 possibilities or evens have only
RW> 2 possibilities. You said there was only one possilibity for the 7-th
123456789
---------
5
That leaves 8 possibilities. Since there are 4 even and 4 odd, and divisible by
even always end in even, that means that all evens go to the evens and all odds
to the odds.
123456789
---------
121252121
3434 4343
7676 6767
9898 8989
Since that means that the evens have an odd for the tens digit and all numbers
divisible by 4 with an odd tens are either 2 or 6 in the ones, leaving 4 and 8
for 2 and 6.
123456789
---------
141254121
3836 8363
7 7 7 7
9 9 9 9
From this, I computed the number of possible solutions. I cannot remember what
I computed, but because the third digit only allows certain combos to pass, the
number of combinations after the third are far less than 32, as you might
believe. You have two possibilities for the next three digits. One with 2 in
the 4 and one with a 6. The 5 is a given. The 6 is a given, as there aren't two
different numbers with the same modulus as 3 had.
SL> the digits required.
RW> 2 possibilities. You said there was only one possilibity for the 7-th
RW> digit (?), but that's not true. It may be xxxxxx2xx or xxxxxx9xx. How
All of the evens are reserved for the evens. That means that 7 is a given. 8
can be figured out easily (7 and 8 are where most of the possibilities dropped
out, beyond the 12 that didn't live beyond 3), and 9 is extraneous, because all
9! of the possibilities are divisible by 9.
I hope this answers your question, because the proof paper in question is
turning to compost at the Cedar Rapids Municipal Mt. Trashmore and I had to
make this up as I go, and I can't list my work, at least not without the
duldrums of making it up all over again. :)
------------------------------------------------------------------------------